#include <stdio.h>
#include <stdlib.h>

#include "redblack.h"
#include "util.h"

int rb_insert(treenode_t **head, int value) {

   int retval;
   treenode_t *search, *new;

   /*
    * Se head eh vazio, significa que o noh inserido
    * sera a "raiz da arvore"
    */
   if(*head == NULL) {

      /* A raiz eh SEMPRE negra */
      *head = (treenode_t *) rMalloc(sizeof(treenode_t));
      (*head)->color=BLACKNODE;
      (*head)->value=value;
      (*head)->right=NULL;
      (*head)->left=NULL;
      (*head)->parent=NULL;

      retval = ADD_HEAD_OK;

   } else {

      search = rb_search(*head, value, QUIET);

      /* Verifica se o valor jah existe na arvore */
      if(search->value == value) retval = ADD_NODE_EXISTS;
      else {

         new = (treenode_t *) rMalloc(sizeof(treenode_t));
         new->value=value;
         new->color=REDNODE;
         new->parent=search;
         new->left=NULL;
         new->right=NULL;

         /* Se valor adicionador eh maior que o pai, eh colocado na direita
          * caso contratrio eh colocado na esquerda */
         if(value > search->value) search->right = new;
         else search->left = new;

         /*
          * Enquanto o noh adicionado possui um avo
          * faz-se a verificacao de balenceamento de cores/arvore
          */
         while( search != NULL && search->parent != NULL) {

            /*
             * Se o noh adicionado e o pai sao vermelhos,
             * temos 4 casos a verificar
             */
            if(search->color != BLACKNODE && new->color != BLACKNODE) {

               treenode_t *uncle = NULL;

               /* Primeiro de tudo o tio eh colocado em um ponteiro */
               if(search->parent != NULL) {
                  if( (search->parent)->left == search) uncle = (search->parent)->right;
                  else if( (search->parent)->right == search) uncle = (search->parent)->left;
               }

               /* Se o pai e o tio do novo item forem rubros, o vo vira rubro e pais pretos */
               if(search->color == REDNODE && uncle != NULL && uncle->color == REDNODE) {

                  if( search->parent != NULL ) {
                     /* Se o vo nao tem pai, eh a raiz, e deve ser preta */
                     if( (search->parent)->parent != NULL )
                        (search->parent)->color = REDNODE;

                   //  else
                        //(search->parent)->color = BLACKNODE;

                  }
                  search->color = BLACKNODE;
                  uncle->color = BLACKNODE;

               /* Se o pai eh rubro, e tio eh negro (ou sem tio), temos 4 excessoes */
               } else if(search->color == REDNODE && ( (uncle != NULL && uncle->color == BLACKNODE) || uncle == NULL) ) {

                  /*
                   * Se o novo noh eh filho esquerdo, e o pai eh filho esquerdo do avo
                   * Faz uma rotacao simples para a direita
                   */
                  if(new->value < search->value && search->parent != NULL && (search->parent)->left == search) {

                     search->color = BLACKNODE;
                     (search->parent)->color = REDNODE;
                     rb_rotate(head, search->parent, RIGHT);

                  /*
                   * Se o novo noh eh filho esquerdo, e o pai eh filho direito do avo
                   * Faz uma rotacao dupla para a esquerda
                   */
                  } else if(new->value < search->value && search->parent != NULL && (search->parent)->right == search) {

                     new->color = BLACKNODE;
                     (search->parent)->color = REDNODE;
                     rb_rotate(head, new->parent, RIGHT);
                     rb_rotate(head, new->parent, LEFT);

                  /*
                   * Se o novo noh eh filho direito, e o pai eh filho direito do avo
                   * Faz uma rotacao simples para a esquerda
                   */
                  } else if(new->value > search->value && search->parent != NULL && (search->parent)->right == search) {

                     search->color = BLACKNODE;
                     (search->parent)->color = REDNODE;
                     rb_rotate(head, search->parent, LEFT);


                  /*
                   * Se o novo noh eh filho direito, e o pai eh filho esquerdo do avo
                   * Faz uma rotacao dupla para a direita
                  */
                  } else if(new->value > search->value && search->parent != NULL && (search->parent)->left == search) {

                     new->color = BLACKNODE;
                     (search->parent)->color = REDNODE;
                     rb_rotate(head, new->parent, LEFT);
                     rb_rotate(head, new->parent, RIGHT);

                  } else retval = ADD_ERROR;
 
               } else retval = ADD_ERROR;


            }

            /* Continua a fazer balanceamento apartir do avo */
            new = search->parent;
            if(search->parent != NULL) search = (search->parent)->parent;

         }

         retval = ADD_NODE_OK;

      }

   }

   return retval;

}

/*
Procurar por um elemento com um valor, se acha, retorna o noh da arvore, se nao retorna o pai do local onde o noh deveria estar
*/
treenode_t *rb_search(treenode_t *head, int value, int mode) {

   treenode_t *search;

   if(head == NULL) {
      if(mode==VERBOSE) printf("Arvore vazia\n");
      return NULL;
   }

   /* Comeca a procurar apartir da raiz (topo), obviamente! */
   search = head;
   while(search != NULL) {

      if(mode==VERBOSE) printf("%d(%d)", search->value, search->color);

      if(value > search->value) {

         if(mode==VERBOSE) printf(" D");
         if(search->right != NULL)
            search = search->right;
         else break;

      } else if(value < search->value) {
         
         if(mode==VERBOSE) printf(" E");
         if(search->left != NULL)
            search = search->left;
         else break;

      } else break;

      if(mode==VERBOSE) printf(" -> ");

   }

   if(mode==VERBOSE) {
      if(search->value != value) printf(" -> ?");
      printf("\n");
   }

   return search;

}

/* Faz a rotaco de um noh da arvore dada a direcao mode=(LEFT - esquerda, RIGHT - direita) */
void rb_rotate(treenode_t **head, treenode_t *node, int mode) {

   treenode_t *tmp;

   if(mode == LEFT) {

      tmp = node->right;

      if(tmp != NULL) node->right = tmp->left;
      if(tmp->left != NULL) (tmp->left)->parent = node;

      if( node->parent != NULL) {
         if( (node->parent)->left == node)
            (node->parent)->left = tmp;
         else
            (node->parent)->right = tmp;
      } else *head = tmp;

      tmp->parent = node->parent;
      node->parent = tmp;
      tmp->left = node;

   } else if(mode == RIGHT) {

      tmp = node->left;

      if(tmp != NULL) node->left = tmp->right;
      if(tmp->right != NULL) (tmp->right)->parent = node;

      if( node->parent != NULL) {
         if( (node->parent)->left == node)
            (node->parent)->left = tmp;
         else
            (node->parent)->right = tmp;
      } else *head = tmp;

      tmp->parent = node->parent;
      node->parent = tmp;
      tmp->right = node;

   }

   return;

}

/* Remove um noh da arvore, retornando o ponteiro para esse noh
 * Obviamente esse noh nao foi limpo ( free() ) e deve ser apos o uso da funcao */
treenode_t *rb_remove(treenode_t **head, int value) {

   treenode_t *search, *tmp, *brother=NULL;

   search = rb_search(*head, value, QUIET);
   if(search != NULL) {

      /*
       * Caso a noh que esteja removendo seja uma folha vermelha
       * Simplesmente libera a memoria e arruma o pai
       */
      if(search->color == REDNODE && search->left == NULL && search->right == NULL) {
         if(search->parent != NULL) {
            if( (search->parent)->left == search)
               (search->parent)->left = NULL;
            else
               (search->parent)->right = NULL;
         }
         return search;

      /*
       * Caso seja preto e soh tenha um filho rubro
       * Coloca filho no lugar, alterando cor para preto
       */
      } else if( search->color == BLACKNODE && (( (tmp=search->left) != NULL
                 && tmp->color == REDNODE && search->right == NULL) ||
                 ( (tmp=search->right) != NULL && tmp->color == REDNODE
                 && search->left == NULL)) ) {

         if(search->parent != NULL) {

           if( (search->parent)->left == search)
              (search->parent)->left = tmp;
           else
              (search->parent)->right = tmp;

         }
         tmp->color = search->color;
         tmp->parent = search->parent;
         if(search == (*head) ) *head = tmp;
         return search;

      /*
       * Caso seja preto e nao tenha filhos
       * faz as verificacoes de tio e rotacoes necessarias
       */
      } else if( search->color == BLACKNODE && search->left == NULL && search->right == NULL) {

         if(search->parent != NULL) {

            /* Caso o noh seja filho esquerdo */
            if( (search->parent)->left == search) {

               brother = (search->parent)->right;

               if(brother != NULL) {

                  /*
                   * Se irmao tem filho esquerdo sendo ele rubro e nao tem do lado direito
                   * precisamos de 1 rotacao para a direita e outra para a esquerda para
                   * balancear a arvore de forma correta
                   */
                  if( (tmp=brother->left) != NULL && tmp->color == REDNODE && brother->right == NULL) {

                     rb_rotate(head, tmp->parent, RIGHT);
                     rb_rotate(head, tmp->parent, LEFT);
                     if( (*head)->color == REDNODE) (*head)->color = BLACKNODE;
                     (search->parent)->color = search->color;

                  /*
                   * Se o irmao possui um filho do lado direito e eh rubro
                   * o irmao passa a ser rubro, filho do irmao preto e pai preto
                   * e eh feita uma rotacao a esquerda para balanceamento
                   */
                  } else if( (tmp=brother->right) != NULL && tmp->color == REDNODE ) {

                     brother->color = BLACKNODE;
                     tmp->color = BLACKNODE;
                     (brother->parent)->color = BLACKNODE;
                     rb_rotate(head, brother->parent, LEFT);
                     if( (*head)->color == REDNODE) (*head)->color = BLACKNODE;

                  /* Se o irmao tem cor vermelha, pai passa a ser vermelho e 
                   * irmao a preto, fazendo uma removao extra pelo pai e depois verificando */
                  } else if(brother->color == REDNODE) {

                     (brother->parent)->color = REDNODE;
                     brother->color = BLACKNODE;
                     rb_remove_extra(head, search);

                  /* Se irmao eh preto, repetimos caso anterior, mas com relacao ao pai */
                  } else if (brother->color == BLACKNODE) {

                     brother->color = REDNODE;
                     (search->parent)->left = NULL;
                     rb_remove_extra(head, search->parent);

                  /* Falhando as comparacoes, soh pecisamos setar o irmao como vermelho
                   * e o pai como preto */
                  } else {
                     brother->color = REDNODE;
                     (brother->parent)->color = BLACKNODE;
                  }

               }

               (search->parent)->left = NULL;

            /* filho direito */
            } else {

               brother = (search->parent)->left;

               if(brother != NULL) {

                  /*
                   * Se irmao tem filho direito sendo ele rubro e nao tem do lado esquerdo 
                   * precisamos de 1 rotacao para a esquerda e outra para a direita para
                   * balancear a arvore de forma correta
                   */
                  if( (tmp=brother->right) != NULL && tmp->color == REDNODE && brother->left == NULL) {

                     rb_rotate(head, tmp->parent, LEFT);
                     rb_rotate(head, tmp->parent, RIGHT);
                     if( (*head)->color == REDNODE) (*head)->color = BLACKNODE;
                     (search->parent)->color = search->color;

                  /*
                   * Se o irmao posui um filho do lado esquerdo e eh rubro
                   * o irmao passa a ser rubro, filho do irmao a preto e pai preto,
                   * feita uma rotacao a esquerda para balanceamento
                   */
                  } else if( (tmp=brother->left) != NULL && tmp->color == REDNODE ) {

                     brother->color = REDNODE;
                     tmp->color = BLACKNODE;
                     (brother->parent)->color = BLACKNODE;
                     rb_rotate(head, brother->parent, RIGHT);
                     if( (*head)->color == REDNODE) (*head)->color = BLACKNODE;

                  /* Se o irmao tem cor vermelha, pai passa a ser vermelho e 
                   * irmao a preto, fazendo uma removao extra pelo pai e depois verificando */
                  } else if(brother->color == REDNODE) {

                     (brother->parent)->color = REDNODE;
                     brother->color = BLACKNODE;
                     rb_remove_extra(head, search);

                  /* Se irmao eh preto, repetimos caso anterior, mas com relacao ao pai */
                  } else if (brother->color == BLACKNODE) {

                     brother->color = REDNODE;
                     (search->parent)->right = NULL;
                     rb_remove_extra(head, search->parent);

                  }

               }

               (search->parent)->right = NULL;

            }


         }

         return search;

      /*
       * Se nada pode ser feito, acha um noh para colocar no lugar
       * descendo um a direita e todo resto a esquerda, poderia ser inverso
       */
      } else {

         treenode_t * save = search;
         if(search->right != NULL) {
            search = search->right;
            while( search != NULL && search->left != NULL) search = search->left;
            printf("corrente %d\n", search->value);
         } else if (search->left != NULL) {
            search = search->left;
            while( search != NULL && search->right != NULL) search = search->right;
            printf("corrente %d\n", search->value);
         }

         tmp = rb_remove(head, search->value);
         if(*head == save) *head = tmp;
         tmp->parent = save->parent;
         if( save->parent != NULL) {
            if( (save->parent)->left == save)
               (save->parent)->left = tmp;
            else
               (save->parent)->right = tmp;
         }
        
         tmp->right = save->right;
         tmp->left = save->left;
         if(tmp->right != NULL) (tmp->right)->parent = tmp;
         if(tmp->left != NULL) (tmp->left)->parent = tmp;
         tmp->color = save->color;
         return save;


      }

   }

   return search;

}

void rb_remove_extra(treenode_t **head, treenode_t *node) {

   treenode_t *tmp;

   if( (node->parent)->right == node) {

      ((node->parent)->left)->color = BLACKNODE;
      (node->parent)->color = REDNODE;
      rb_rotate(head, node->parent, RIGHT);

      tmp = (node->parent)->left;
      if( tmp->left != NULL && (tmp->left)->color == REDNODE ) {
         rb_rotate(head, tmp->parent, RIGHT);
         tmp->color = REDNODE;
         (tmp->left)->color = BLACKNODE;
         (tmp->right)->color = BLACKNODE;
      } else if( tmp->left == NULL && (tmp=tmp->right) != NULL && tmp->color == REDNODE ) {
         rb_rotate(head, tmp->parent, LEFT);
         rb_rotate(head, tmp->parent, RIGHT);
         tmp->color = REDNODE;
         (tmp->left)->color = BLACKNODE;
         (tmp->right)->color = BLACKNODE;
      }

   } else if( (node->parent)->left == node) {

      ((node->parent)->right)->color = BLACKNODE;
      (node->parent)->color = REDNODE;
      rb_rotate(head, node->parent, LEFT);

      tmp = (node->parent)->right;
      if( tmp->right != NULL && (tmp->right)->color == REDNODE ) {
         rb_rotate(head, tmp->parent, LEFT);
         tmp->color = REDNODE;
         (tmp->right)->color = BLACKNODE;
         (tmp->left)->color = BLACKNODE;
      } else if( tmp->right == NULL && (tmp=tmp->left) != NULL && tmp->color == REDNODE ) {
         rb_rotate(head, tmp->parent, RIGHT);
         rb_rotate(head, tmp->parent, LEFT);
         tmp->color = REDNODE;
         (tmp->right)->color = BLACKNODE;
         (tmp->left)->color = BLACKNODE;
      }

   }

   return;

}
